package datastructure.tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Given a binary tree, print out the tree in level order (ie, from left to right, level by level).
 * Output a newline after the end of each level.

3
/  \
9   20
/  \
15    7

For example, the level order output of the tree above is:

3
9 20
15 7

 *
 * @author Lei
 */
public class PrintLevelOrder {

    public static void printLevelOrder(TreeNode root) {
        if (root == null) {
            return;
        }

        int currentLevelNodeCount = 1;
        int nextLevelNodeCount = 0;

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);

        while (!queue.isEmpty()) {
            TreeNode n = queue.poll();
            currentLevelNodeCount--;

            if (n.left != null) {
                queue.add(n.left);
                nextLevelNodeCount++;
            }

            if (n.right != null) {
                queue.add(n.right);
                nextLevelNodeCount++;
            }

            System.out.print(n.value + " ");
            if (currentLevelNodeCount == 0) {
                System.out.println(" ");

                currentLevelNodeCount = nextLevelNodeCount;
                nextLevelNodeCount = 0;

            }
        }
    }

    public static void main(String[] args) {

        TreeNode n1 = new TreeNode(1);
        TreeNode n2 = new TreeNode(2);
        TreeNode n3 = new TreeNode(3);
        TreeNode n4 = new TreeNode(4);
        TreeNode n5 = new TreeNode(5);
        TreeNode n6 = new TreeNode(6);

        n5.left = n2;
        n5.right = n6;

        n2.left = n1;
        n2.right = n4;

        n4.left = n3;

        PrintLevelOrder.printLevelOrder(n5);


    }
}
